
/*
 * Gustavo Sanchez 10313 
 * Algoritmos y estructura de datos
 * Seccion: 20
 */
import java.util.InputMismatchException;
import java.util.Random;
import java.util.List;
import java.util.Scanner;

public class Sort {
    public static void main(String[] args){
    	int dato[];
    	int opcion;
    	do{
    		System.out.println("\n |                         Menu                    |");
			System.out.println("\n |              1. Seleccion sort                  |");
			System.out.println("\n |              2. Quick sort                      |");
			System.out.println("\n |              3. Seleccion sort a lista ordenada |");
			System.out.println("\n |              4. Quicksort a lista ordenada      |");
			System.out.println("\n |              5. Salir                           |");
    		System.out.println("\n Ingrese el numero de la opcion que desee: ");
    		opcion=entrada(5,1);
        	System.out.println("Cuantos numeros aleatorios desea generar?(10-2000)");
        	int numeros=entrada(2000,10);
        	dato=new int[numeros];
        	dato=generar(numeros);
    		switch(opcion){
    			case 1:
    				selectionSort(dato, numeros);
    				break;
    			case 2:
    				quickSort(dato, numeros);
    			case 3:
    				selectionSort(dato, numeros);
    				selectionSort(dato, numeros);
    			case 4:
    				quickSort(dato, numeros);
    				quickSort(dato, numeros);
    				break;
    			default:
    				
    			break;
    		}
    	}while(opcion<5);
    	
    	
    }
    public static int[] generar(int numero){
    	int datos[]=new int[numero];
    	Random generator=new Random();
    	for(int x=0; x<numero;x++){
    		datos[x]=generator.nextInt();
    	}
    	return datos;
	}
    public static void selectionSort(int data[], int n)
    // pre: 0 <= n <= data.length
    // post: values in data[0..n-1] are in ascending order
    {
        int numUnsorted = n;
        int index; // general index
        int max; // index of largest value
        while (numUnsorted > 0)
        {
            // determine maximum value in array
            max = 0;
            for (index = 1; index < numUnsorted; index++)
            {
                if (data[max] < data[index]) max = index;
            }
            swap(data,max,numUnsorted-1);
            numUnsorted--;
        }
    }
    private static int partition(int data[], int left, int right)
// pre: left <= right
// post: data[left] placed in the correct (returned) location
    {
        while (true)
        {
            // move right "pointer" toward left
            while (left < right && data[left] < data[right]) right--;
            if (left < right) swap(data,left++,right);
            else return left;
            // move left pointer toward right
            while (left < right && data[left] < data[right]) left++;
            if (left < right) swap(data,left,right--);
            else return right;
        }
    }
    public static void quickSort(int data[], int n)
    // post: the values in data[0..n-1] are in ascending order
    {
    quickSortRecursive(data,0,n-1);
    }
    private static void quickSortRecursive(int data[],int left,int right)
    // pre: left <= right
    // post: data[left..right] in ascending order
    {
        int pivot; // the final location of the leftmost value
        if (left >= right) return;
        pivot = partition(data,left,right); /* 1 - place pivot */
        quickSortRecursive(data,left,pivot-1); /* 2 - sort small */
        quickSortRecursive(data,pivot+1,right);/* 3 - sort large */
        /* done! */
    }
    public static void swap(int data[], int i, int j)
    // pre: 0 <= i,j < data.length
    // post: data[i] and data[j] are exchanged
    {
        int temp;
        temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
	public static int entrada(int max, int min){
		Scanner readln=new Scanner(System.in);
		int x=0;
		do{
			try{
			
				x=readln.nextInt();
				
				
				if((x>max)||(x<min))
					throw new InputMismatchException();
			}
			catch(InputMismatchException exception){
				x=10;
			}
		}while(x==0);
		return x;
			
	}
    
}
